package com.ldy.thoughtWorks.question1;

import org.junit.Before;
import org.junit.Test;

import java.util.*;

/**
 * 面试题第一题Junit测试。<br>
 * 版权: Copyright (c) 2011-2018<br>
 * 公司: 活力天汇<br>
 *
 * @author: 刘德咏<br>
 * @date: 2018-07-25<br>
 */
public class Question1Test {


    private Map<String, Node> nodeMap = new HashMap<>();

    @Before
    public void before() {
        init();
    }

    // question one
    @Test
    public void testABC() {
        List<String> route = new ArrayList<>();
        // 计算路线图 A - B - C 结果为9
        route.add("A");
        route.add("B");
        route.add("C");
        System.out.println(computerRouteLength(route));
    }

    // question two
    @Test
    public void testAD() {
        List<String> route = new ArrayList<>();
        route.add("A");
        route.add("D");
        System.out.println(computerRouteLength(route));
    }

    // question three
    @Test
    public void testADC() {
        List<String> route = new ArrayList<>();
        route.add("A");
        route.add("D");
        route.add("C");
        System.out.println(computerRouteLength(route));
    }

    // question four
    @Test
    public void testAEBCD() {
        List<String> route = new ArrayList<>();
        route.add("A");
        route.add("E");
        route.add("B");
        route.add("C");
        route.add("D");
        System.out.println(computerRouteLength(route));
    }

    // question five
    @Test
    public void testAED() {
        List<String> route = new ArrayList<>();
        route.add("A");
        route.add("E");
        route.add("D");
        System.out.println(computerRouteLength(route));
    }

    // question six   <= stopCount
    @Test
    public void testStopCount() {
        Map<String, Integer> result = computerTwoTownStopCount("C", "C", 3, false);
        if (result == null || result.size() == 0) {
            System.out.println("不存在这样的路线");
            return;
        }
        for (Map.Entry entry : result.entrySet()) {
            System.out.println("路线" + entry.getKey() + ":距离" + entry.getValue());
        }

    }

    // question seven   == stopCount
    // 我认为 ADCDC， DC段重复，不纳入参考。
    @Test
    public void testStopCountEaque() {
        Map<String, Integer> result  = computerTwoTownStopCount("A", "C", 4, true);
        if (result == null || result.size() == 0) {
            System.out.println("不存在这样的路线");
            return;
        }
        for (Map.Entry entry : result.entrySet()) {
            System.out.println("路线" + entry.getKey() + ":距离" + entry.getValue());
        }
    }

    // question eight 测试从A-C最短的路线。
    @Test
    public void testTheShortestRouteAC() {
        // 不限中转次数，就默认设置为100
        Map<String, Integer> result  = computerTwoTownStopCount("A", "C", 100, false);
        if (result == null || result.size() == 0) {
            System.out.println("不存在这样的路线");
            return;
        }
        System.out.println("------符合路线有 ---------------");
        for (Map.Entry entry : result.entrySet()) {
            System.out.println("路线" + entry.getKey() + ":距离" + entry.getValue());
        }
        // 取最小的路线
        System.out.println("-------------------------------");
        System.out.println("最短距离：" + Collections.min(result.values()));
    }

    // question nine 测试从B-B最短的路线。
    @Test
    public void testTheShortestRouteBB() {
        // 不限中转次数，就默认设置为100
        Map<String, Integer> result  = computerTwoTownStopCount("B", "B", 100, false);
        if (result == null || result.size() == 0) {
            System.out.println("不存在这样的路线");
            return;
        }
        System.out.println("------符合路线有 ---------------");
        for (Map.Entry entry : result.entrySet()) {
            System.out.println("路线" + entry.getKey() + ":距离" + entry.getValue());
        }
        // 取最小的路线
        System.out.println("-------------------------------");
        System.out.println("最短距离：" + Collections.min(result.values()));
    }

    // question ten 测试从C-C 距离小于30
    @Test
    public void testTheShortestRouteCC() {
        // 不限中转次数，就默认设置为100
        Map<String, Integer> result  = computerTwoTownStopCountV2("C", "C", 30);
        if (result == null || result.size() == 0) {
            System.out.println("不存在这样的路线");
            return;
        }
        System.out.println("------符合路线有 ---------------");
        for (Map.Entry entry : result.entrySet()) {
            System.out.println("路线" + entry.getKey() + ":距离" + entry.getValue());
        }
        // 取最小的路线
        System.out.println("-------------------------------");
        System.out.println("最短距离：" + Collections.min(result.values()));
    }

    /**
     * 返回长度
     * @param route 路线图
     * @return 长度
     */
    public int computerRouteLength(List<String> route) {
        if (route == null || route.size() < 2) {
            System.out.println("路线图为空或则路线图小于2");
            return 0;
        }
        String firstNodeName = route.get(0);
        Node currentNode = nodeMap.get(firstNodeName);
        if (currentNode == null) {
            System.out.println("路线图找不到首节点");
            return 0;
        }
        // 检索此路线
        StringBuilder line = new StringBuilder(currentNode.getName());
        int distance = 0;
        for (int i = 1; i < route.size(); i++) {
            Set<Route> routes = currentNode.getRoutes();
            Iterator<Route> iterator = routes.iterator();
            int count = 0;
            int maxItem = routes.size();
            while (iterator.hasNext()) {
                Route tempRoute = iterator.next();
                // 遍历次数到达最后一次，还没有找到路线中的节点
                if (++count == maxItem && !route.get(i).equals(tempRoute.getNode().getName())){
                    System.out.println("没有找到此路线："+ line.substring(line.length()-1) + "->" + route.get(i));
                    return 0;
                }
                // 匹配到对的节点
                if (route.get(i).equals(tempRoute.getNode().getName())) {
                    line.append(route.get(i));
                    // 当前节点往后移动一位
                    currentNode = tempRoute.getNode();
                    distance += tempRoute.getWeight();
                    break;
                }
            }
        }
        return distance;
    }

    private Map<String, Integer> result = new HashMap<>();

    /**
     * 计算从起始地到目的地中转次数 <= stopCount
     * @param dep 起始地
     * @param arr 目的地
     * @param stopCount 中转次数
     * @param strictEqalsStopCount 是否严格控制相等中转次数
     * @return 符合结果的路线图。
     */
    public Map<String, Integer> computerTwoTownStopCount(String dep, String arr, int stopCount, Boolean strictEqalsStopCount) {
        if (dep == null || dep.length() == 0) {
            System.out.println("出发地为空");
            return null;
        }
        if (arr == null || arr.length() == 0) {
            System.out.println("目的地为空");
            return null;
        }

        Node currentNode = nodeMap.get(dep);
//        这里不能用对象，否则递归会把这个对象一只传递下去，导致不是想要的结果。
//        StringBuilder line = new StringBuilder(currentNode.getName());
        int transferCount = 0;
        int distance = 0;
        String line = new String(currentNode.getName());
        dfs(currentNode, distance, line, arr, transferCount, stopCount, strictEqalsStopCount);
        return result;
    }

    /**
     * 计算从起始地到目的地中转次数 <= stopCount
     * @param dep 起始地
     * @param arr 目的地
     * @param maxDistance 最大距离
     * @return 符合结果的路线图。
     */
    public Map<String, Integer> computerTwoTownStopCountV2(String dep, String arr, int maxDistance) {
        if (dep == null || dep.length() == 0) {
            System.out.println("出发地为空");
            return null;
        }
        if (arr == null || arr.length() == 0) {
            System.out.println("目的地为空");
            return null;
        }
        Node currentNode = nodeMap.get(dep);
        String line = new String(currentNode.getName());
        boolean firstLogin = true;
        dfsV2(currentNode, 0, line, arr, maxDistance, firstLogin);
        return result;
    }


    /**
     * 深度优先遍历算法
     * @param node 遍历的当前节点
     * @param distance 当前路线的总长度
     * @param line 当前路径
     * @param arr 到达截止点停止遍历
     * @param transferCount 当前中转次数
     * @param stopCount 截止中转次数
     * @param strictEqalsStopCount 严格相等中转次数
     */
    public void dfs(Node node, int distance, String line, String arr, Integer transferCount, int stopCount, Boolean strictEqalsStopCount) {
        if (transferCount > stopCount) {
//            System.out.println("中转次数大于最大中转次数，递归停止");
            // 将line 回溯
            return;
        }

        Set<Route> routes = node.getRoutes();
        distance = getDistance(node, distance, line);

        // transferCount > 0 防止闭环
        // 判断中转次数是否完全，亦或则是小于登录，为了区分question6和question7。
        Boolean condition;
        if (strictEqalsStopCount) {
            condition = node.getName().equals(arr) && transferCount == stopCount && transferCount > 0;
        } else {
            condition = node.getName().equals(arr) && transferCount <= stopCount && transferCount > 0;
        }
        if (condition) {
            // 找到此节点
//            System.out.println(line.toString());
            result.put(line.toString(), distance);
            return;
        }
        // 中转次数加1
        transferCount += 1;
        Iterator<Route> iterator = routes.iterator();
        while (iterator.hasNext()) {
            Route next = iterator.next();
            Node nextNode = next.getNode();
            // 找到重复路径退出
            if (line.toString().contains(node.getName() + nextNode.getName())) {
//                System.out.println("遇到重复路径退出" + node.getName() + nextNode.getName());
                return;
            }
            dfs(nextNode, distance, line + nextNode.getName(), arr, transferCount, stopCount, strictEqalsStopCount);
        }
    }

    /**
     * 得到当前节点的上一个节点到当前节点的距离，累加
     * @param node 当前节点
     * @param distance 当前路线的距离
     * @param line 当前路线图
     * @return 得到当前节点的上一个节点到当前节点的距离，累加
     */
    private int getDistance(Node node, int distance, String line) {
        if (line.length() > 1) {
            // 计算line当前节点的父亲节点到当前节点的 距离。
            String prevNodeName = line.substring(line.length() - 2, line.length() - 1);
            Node prevNode = nodeMap.get(prevNodeName);
            Iterator<Route> prevNodeRoute = prevNode.getRoutes().iterator();
            while (prevNodeRoute.hasNext()) {
                Route next = prevNodeRoute.next();
                if (next.getNode().getName().equals(node.getName())) {
                    distance += next.getWeight();
                    break;
                }
            }
        }
        return distance;
    }

    /**
     * 深度优先遍历算法
     * @param node 遍历的当前节点
     * @param distance 当前路线的总长度
     * @param line 当前路径
     * @param arr 到达截止点停止遍历
     * @param maxDistance 最大多长距离退出
     * @param firstLogin 是否是第一次进入
     */
    public void dfsV2(Node node, int distance, String line, String arr, int maxDistance, boolean firstLogin) {

        Set<Route> routes = node.getRoutes();
        distance = getDistance(node, distance, line);
        // distance < maxDistance  , 并且当前节点是目的地节点，而且map中不含此路线
        if (distance < maxDistance && ! result.containsKey(line) && node.getName().equals(arr) && !firstLogin) {
            // 找到不重复节点, 这里调用栈不终止。
            result.put(line.toString(), distance);
        }
        if (distance >= maxDistance){
            return;
        }
        firstLogin = false;
        Iterator<Route> iterator = routes.iterator();
        while (iterator.hasNext()) {
            Route next = iterator.next();
            Node nextNode = next.getNode();
            dfsV2(nextNode, distance, line + nextNode.getName(), arr, maxDistance, firstLogin);
        }
    }


    /**
     * 初始化有向图
     */
    public void init() {
        Node A = new Node("A");
        Node B = new Node("B");
        Node C = new Node("C");
        Node D = new Node("D");
        Node E = new Node("E");

        Set<Route> aroutes = new HashSet<>();
        Set<Route> broutes = new HashSet<>();
        Set<Route> croutes = new HashSet<>();
        Set<Route> droutes = new HashSet<>();
        Set<Route> eroutes = new HashSet<>();
        Route ab5 = new Route(B, 5);
        Route ad5 = new Route(D, 5);
        Route ae7 = new Route(E, 7);
        aroutes.add(ab5);
        aroutes.add(ad5);
        aroutes.add(ae7);
        A.setRoutes(aroutes);

        Route bc4 = new Route(C, 4);
        broutes.add(bc4);
        B.setRoutes(broutes);

        Route cd8 = new Route(D, 8);
        Route ce2 = new Route(E, 2);
        croutes.add(cd8);
        croutes.add(ce2);
        C.setRoutes(croutes);

        Route de6 = new Route(E, 6);
        Route dc8 = new Route(C, 8);
        droutes.add(de6);
        droutes.add(dc8);
        D.setRoutes(droutes);

        Route eb3 = new Route(B, 3);
        eroutes.add(eb3);
        E.setRoutes(eroutes);

        nodeMap.put(A.getName(), A);
        nodeMap.put(B.getName(), B);
        nodeMap.put(C.getName(), C);
        nodeMap.put(D.getName(), D);
        nodeMap.put(E.getName(), E);
    }
}
